package cn.xaut.周赛.m228;

/**
 * 5677. 统计同构子字符串的数目
 */
public class demo5677 {

    public int countHomogenous(String s) {

        int len = s.length();
        if (len < 2)
            return len;

        // dp[i] 表示 i个相同的字母所能构成的同构子字符串的数目
        int[] dp = new int[len + 1];
        
        // 初始化
        dp[1] = 1;
        
        // 状态转移
        for (int i = 2; i <= len; i++) 
            dp[i] = (dp[i - 1] + i) % MOD;
        
        int sum = 0;
        char[] cs = s.toCharArray();
        int length = 1;
        for (int i = 0; i < len - 1; i++) {
            if (cs[i] == cs[i + 1]) {
                length ++;
            } else {
                sum += dp[length];
                length = 1;
            }
        }
        sum += dp[length];  // 最后一次遍历少加了个 dp[length]
        
        return sum;
    }

    
    public static final int MOD = (int) (1e9 + 7);
    // 超时
    public int countHomogenous2(String s) {

        int len = s.length();
        if (len < 2)
            return len;
        char[] cs = s.toCharArray();
        int sum = 0;
        
        for (int i = 0; i < len; i ++) {
            
            int j = i;
            while (j + 1 < len && cs[j + 1] == cs[i])
                j++;
            sum += (j - i + 1) % MOD;
        }
        
        return sum;
    }

    public int countHomogenous3(String s) {

        int len = s.length();
        if (len < 2)
            return len;
        char[] cs = s.toCharArray();
        int sum = 0;
        for (int i = 0; i < len;) {

            int j = i + 1;
            while (j < len && cs[j] == cs[i])
                j ++;
            int k = j - i;
            sum = (sum + k * (k + 1) / 2) % MOD;
            i = j;
        }

        return sum;
    }


        public static void main(String[] args) {

        System.out.println(new demo5677().countHomogenous3("abbcccaa")); // 13
        System.out.println(new demo5677().countHomogenous3("xy")); // 2
        System.out.println(new demo5677().countHomogenous3("zzzzz")); // 15
        System.out.println((int)1e2);    // 100
        System.out.println((int)(1e9+7));
    }
}
